洛谷 P1197 [JSOI2008]星球大战 题解

发表于 | 分类于 | | 热度: ℃

Description

给你一张 $n$ 个点 $m$ 条边无向图，$k$ 次操作，每次去掉一个点和与其相连的所有边，问每次操作后的联通块个数。

数据范围：$1≤n≤400000 , 1≤m≤200000$

Solution

每次删掉一个点不太容易，但是可以反过来想：先去掉所有该去掉的点，然后一个点一个点往上加。

使用并查集来判断联通情况。倒过来枚举 $k$ 个点，找到与该点相连的点，如果不在一个集合内，联通块个数 $-1$，把这两个点添加到同一个集合内。

注意：已经被去掉的点不算一个联通块。在每次加点的时候，联通块个数个数都要先 $+1$。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;

const int N = 500000;
struct edge
{
    int nxt, to;
} e[N];
int n, m, k, cnt = 0, now;
int head[N], f[N], a[N], b[N], c[N], ans[N];
bool kill[N];

void add(int x, int y)
{
    e[++cnt] = (edge) { head[x], y };
    head[x] = cnt;
}

int find(int x)
{
    if(f[x] == x) return x;
    return f[x] = find(f[x]);
}

int main()
{
    scanf("%d%d", &n, &m);
    memset(head, 0, sizeof(head));
    for(int i = 1; i <= m; i++)
    {
        scanf("%d%d", &a[i], &b[i]);
        a[i]++, b[i]++;
        add(a[i], b[i]);
        add(b[i], a[i]);
    }
    scanf("%d", &k);
    memset(kill, false, sizeof(kill));
    for(int i = 1; i <= k; i++)
    {
        scanf("%d", &c[i]);
        c[i]++;
        kill[c[i]] = true;
    }
    now = n - k;
    for(int i = 1; i <= n; i++) f[i] = i;
    for(int i = 1; i <= m; i++)
        if(!kill[a[i]] && !kill[b[i]] && find(a[i]) != find(b[i]))
        {
            now--;
            f[find(a[i])] = find(b[i]);
        }
    ans[k + 1] = now;
    for(int i = k; i > 0; i--)
    {
        kill[c[i]] = false;
        now++;
        for(int j = head[c[i]]; j; j = e[j].nxt)
        {
            int v = e[j].to;
            if(!kill[v] && find(v) != find(c[i]))
            {
                now--;
                f[find(v)] = find(c[i]);
            }
        }
        ans[i] = now;
    }
    for(int i = 1; i <= k + 1; i++) printf("%d\n", ans[i]);
    return 0;
}